/**
 * @ClassName 插入排序
 * @Description: 将每一个待排序的记录按照其顺序码大小插入到前面已排序的子序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
 * @Author 40919
 * @Date 2020/4/21 0021 16:05
 * @Version v1.0
 **/
public class test {
    public static void main(String[] args) {
        //insetpaixu();  直接插入排序

        //erfeninsetpaixu();   //二分法排序
    }

    //直接插入排序
    private static void insetpaixu() {
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.println("排序之前：");
        for (int i = 0;i<a.length;i++){
            System.out.println(a[i]+" ");
        }
        //直接插入排序
        for (int i = 1;i<a.length;i++){
            //待插入元素
            int temp = a[i];

            int j;
            for ( j = i -1;j>=0;j--){
                //将大于temp的往后移动一位
                if (a[j] > temp ){
                    a[j+1] = a[j];
                }else {
                    break;
                }
            }
            a[ j + 1 ] = temp;
        }
        System.out.println();
        System.out.println("排序之后: ");
        for (int i = 0;i<a.length;i++){
            System.out.println(a[i]+" ");
        }
    }

    //二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。
    private static void erfeninsetpaixu(){
        int [] a = { 49,38,65,97,176,213,227,49,78,34,12,164,11,18,1 };
        System.out.println("排序之前: ");
        for (int i = 0;i<a.length;i++){
            System.out.println(a[i] + " ");
        }
        //二分法插入排序
        sort(a);
        System.out.println();
        System.out.println("排序之后: ");
        for (int i = 0;i<a.length;i++){
            System.out.println(a[i] + "");
        }
    }
    private static void sort(int[] a){
        for(int i = 0;i<a.length;i++){
            int temp = a[i]; //第一个元素
            int left = 0;  //从0位开始
            int right = i-1;  //到几位结束
            int mid = 0;  //中位数
            while (left <= right){
                mid = (right+left)/2;
                if (temp < a[mid]){   //和中位的比较
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j>=left;j--){
                a[ j + 1 ] = a[j];
            }
            if (left != i){
                a[left] = temp;
            }
        }
    }



}
